Find All Numbers Disappeared in an Array

Given an array nums of n integers where nums[i] is in the range [1, n], return an array of all the integers in the range [1, n] that do not appear in nums.

Example 1:

Input: nums = [4,3,2,7,8,2,3,1]
Output: [5,6]

Example 2:

Input: nums = [1,1]
Output: [2]

Constraints:

• n == nums.length

• 1 <= n <= 10^5

• 1 <= nums[i] <= n

My Solution

The key intuition to solving this problem is recognizing that the array nums contains only integers in the range [1,n], where n is the size of the array. Since some of the elements have disappeared, we know that some of the elements in the array are duplicated. We also know that all the numbers are positive. The trick is to mark the elements we have seen by marking the appropriate indices of those elements as we scan the array. We mark them by making the value at the index of the element negative. Finally, once we have scanned all elements we scan the array again, but this time we look for any elements that are positive. A positive element means that the number corresponding to the index was not seen. We add these numbers to our output and return them.

This example illustrates the approach. Suppose we have the following array:

nums : [3,4,3,1,5]

We start scanning the array.

nums : [3,4,3,1,5]
i : 0
nums[i] : 3

A detail here is that since the numbers are from [1,n] and the elements of the array are 0-indexed, we mark the element at nums[i]-1 as negative. After doing that we have the following array:

nums : [3,4,-3,1,5]
i : 1
nums[i] : 4

We mark the element at index 3 (4-1) as negative.

nums : [3,4,-3,-1,5]
i : 2
nums[i] : -3

Another detail here is we take the absolute value of the number to find its index. Also if the number at the index is already negative, we don't update it because we have seen it.

nums : [3,4,-3,-1,5]
i : 3
nums[i] : -1

We update the element at index 0.

nums : [-3,4,-3,-1,5]
i : 4
nums[i] : 5

We update the element at index 4.

nums : [-3,4,-3,-1,-5]

We have iterated through the entire array, so all that needs to be done now is to scan the array again and append the positive elements to the output. The only positive element is 4, at the index 1. Since the indices are 0-indexed and the numbers in the array start at 1, we need to add 1 to the index of the positive number to get the actual number that disappeared.

ans : [2]

Time complexity is O(n) because we scan the array twice, one time to mark all the numbers we see, and another time to capture all the positive elements.

Space complexity is O(1), because we don't require any extra space besides the space required for the output array, which doesn't get included in space complexity analysis.

class Solution {
    public List<Integer> findDisappearedNumbers(int[] nums) {
        List<Integer> out = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            int idx = Math.abs(nums[i]) - 1;
            if (nums[idx] > 0) {
                nums[idx] *= -1;
            }
        }

        for (int i = 0; i < nums.length; i++) {
            if (nums[i] > 0) {
                out.add(i+1);
            }
        }

        return out;
    }
}